class LRUCache {
public:
    struct list{
        int key,value;
        list* prev;
        list* next;
        list():
            key(0),value(0),prev(nullptr),next(nullptr)
            {}
        
        list(int k,int v):
            key(k),value(v),prev(nullptr),next(nullptr)
            {}
    };
                                        
    unordered_map<int,list*> hash;
    list* head;
    list* tail;
    int size;
    int cap;
                                        
    LRUCache(int capacity):cap(capacity),size(0){
        head = new list();
        tail = new list();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(!hash.count(key)){
            return -1;
        }
        list* cur = hash[key];
        moveHead(cur);
        return cur->value;
    }
                                        
    void moveHead(list* cur){
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
        cur->next = head->next;
        head->next->prev = cur;
        cur->prev = head;
        head->next = cur;
    }
                                        
    void addNode(list* cur){
        head->next->prev = cur;
        cur->next = head->next;
        
        head->next = cur;
        cur->prev = head;
    }
    
    list* moveTail(){
        list* cur = tail->prev;
        tail->prev = cur->prev;
        cur->prev->next = tail;
        return cur;
    }
                                        
    void put(int key, int value) {
        if(hash.count(key)){
            list* cur = hash[key];
            cur->value = value;
            moveHead(cur);
        }else{
            list* cur = new list(key,value);
            hash[key] = cur;
            addNode(cur);
            ++size;
            if(size > cap){
                list* moved = moveTail();
                hash.erase(moved->key);
                delete moved;
                --size;
            }
        }
    }
};

